package com.jhy.review.paixu;

import java.util.Arrays;

/**
 * @author go_jhy
 * @create 2022/6/11 - 下午 5:23
 * 改版的快速排序
 * 1、0  每次排好一个数 分为两个部分
 * 2.0   每次排好一些数 分为三个部分
 * 3.0   用随机数 来和最后一个数交换 这样就算出来一个数学期望
 */
public class Code06_QuickSort {


    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;

    }

    //调用的总方法的快排
    public static void quickSort(int[] arr) {
        //老方法了先判断下
        if (arr == null && arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            //生成一个随机数和最后一个数交换 作为我们分区的标志  范围为[0,n)

            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            //分区将这个数左边全是小于的 中间是等于  右边是大于的
            int[] partition = partition(arr, l, r);
            //然和进行递归 左右两边都是这样 我觉得这里存储的是下标  0 1 是之前分区后的下标的值
            quickSort(arr, l, partition[0] - 1);
            quickSort(arr, partition[1] + 1, r);
        }

    }

    public static int[] partition(int[] arr, int l, int r) {
        //先定义左右两个区间的范围
        int less = l - 1;
        //因为最后的一个数用来作为划分的区间了
        int more = r;
        //这个记录下标等于more的时候停止 因为是等于这个标准表值的时候 下标是只加加
        while (l < more) {
            if (arr[l] < arr[r]) {
                //如果当前的数小于标准的那个值 意思就是当前的数（l）和左边的下一个数（++less）交换 然后当前下标的数l++
                swap(arr, ++less, l++);
            } else if (arr[l] > arr[r]) {
                //如果当前的数大于了标准的那个值  那么就是右边的数的前一个值和当前的数交换 但是当前数的下标不会变化
                swap(arr, --more, l);
            } else {
                l++;
            }

        }
        //然后最后这个数 和more当前的值做交换 那么这个数就排序好了
        swap(arr, more, r);
        //存储的是下标 而不是值
        return new int[]{less + 1, more};

    }


    public static void main(String[] args) {
        int[] arr = {5, 7, 6, 4, 3, 5};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}